package hot

/*
原题链接:
https://leetcode.cn/problems/daily-temperatures/

739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]


单调栈:
遍历每日温度, 维护一个单调栈
	* 若栈为空或者当日温度小于栈顶温度, 则直接入栈
	* 反之, 若当日温度大于栈顶温度, 说明栈顶元素的升温日已经找到了, 则将栈顶元素出栈,
	  计算其与当日相差的天数即可
	* 注意题目要求的是升温的天数, 而不是升温后的温度, 因此栈中应该存储下标, 而非温度.
*/
//一刷

//一刷

func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures) //1.获取切片长度，声明结果切片
	res := make([]int, n)

	var st []int //2.声明单调栈切片

	for i := 0; i < n; i++ { //3.遍历气温切片
		for len(st) > 0 && temperatures[i] > temperatures[st[len(st)-1]] { //4.如果单调栈长度 > 0 && 当天温度> 温度数组[栈顶元素索引]
			prevIndex := st[len(st)-1]     //获取栈顶元素
			st = st[:len(st)-1]            //弹出栈顶元素
			res[prevIndex] = i - prevIndex //结果切片存入结果差值
		}

		st = append(st, i) //5.栈中添加i下标
	}
	return res
}
